HW#4 --- last modified February 07 2019 04:29:57..

Solution set.

Due date: Apr 21

Files to be submitted:
  Hw4.zip

Purpose: To learn about different representations of binary search trees. To prove simple properties about trees.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Implement lists, stacks, queues, search trees, heaps, union-find ADT, and graphs and use these data structures in programs they design.

LO2 -- Prove basic properties of trees and graphs.

Specification:

For this homework you will implement four classes: Hw4, Hw4MemoryManager, Hw4Node and Hw4Tree. All classes should be in their own file. I.e., Hw4 should be in the file Hw4.java, Hw4MemoryManager in Hw4MemoryManager.java, etc. All of these files should be included in your Hw4.zip that your submit. Your whole project will be compiled from the command line by the grader using:

javac Hw4.java

Hw4 is the driver program used to test your project. An Hw4MemoryManager is supposed to act as the memory manager for nodes of a binary search tree. Hw4Node is supposed to represent one such node. Hw4Tree is supposed to be an implementation of a binary search tree which uses nodes maintain by a Hw4MemoryManager. Below we describe each of these classes in more detail. Methods we describe are the public methods of these classes. You are allowed to define additional helper methods as long as they are private.

Your implementation of Hw4MemoryManager is only allowed two non-static, non-final fields: an array int[] memory and an int freeHead (you are also allowed public static final constants). memory is declared without any modifiers, freeHead is private. You are only allowed in your code to access the memory field of Hw4MemoryManager within the class itself and within Hw4Node's set and get methods. memory will be used to hold search tree nodes. A search tree node will be implement as four consecutive int's. The first int is used to hold a positive integer representing data, this is followed by an int to hold the index of the parent node, followed by int's for the left and right children respectively. A node is always assumed to start at an array index which is 0 mod 4. freeHead is used to reference a free-space list of nodes in memory which are not in use. It stores the index into memory of the first node in this free space list. Each node in the free space list is also four consecutive int's and is always assumed to start at an array index which is 0 mod 4. The first int is always a negative value (indicating this memory is free). The second int is the index of the previous member in the free space list, the third int is the index of the next element in the list, and the last int is ignored. A negative value for either previous or next indicates the end of the list in that direction. Hw4MemoryManager should support the following methods implemented as described:

Hw4MemoryManager(int numNodes)

Creates a Hw4MemoryManager capable of holding numNode many nodes. This entails allocating the field memory to be able to hold 4*numNode many int's and initializing freeHead to 0. The int's in memory should be initialized so that all int's at indexes of the form 0 mod 4 are -1, the previous int and next int's should be set up correctly and the last int should be 0. I.e., the four int's of node 0, should have values -1, -1, 1, 0; the four int's of node 1 should have values -1, 0, 2, 0, etc. The third component of the last node should be -1 to indicate no more nodes.

Hw4Node allocate() throws OutOfMemoryError

This pops the first item off the freeHead list. To do this, an int tmp is set to freeHead. freeHead is set to the next component of the node freeHead points to. The value component of the four int's of the node referenced by tmp is set to 0 (neither a negative number which would mean free, or a positive number which would be a part of a tree). A new Hw4Node is created using the call node = new Hw4Node(this, tmp); . If freeHead was negative to begin with (because there was no more memory) an OutOfMemoryError should be thrown.

void freeNode(Hw4Node node) throws IndexOutOfBoundsException, NullPointerException

This sets node's value to -1. It is then put onto the free-space list pointed to be freeHead. If node.current is negative or longer than the array then a IndexOutOfBoundsException is thrown, and if memory[node.current] is negative then a NullPointerException is thrown.

void printMemory()

For each int in the Hw4MemoryManager's memory, this prints a space followed by that int. After the last int, it prints a newline.

An Hw4Node has two fields: Hw4MemoryManager manager, and int current. We assume that the first is a reference to the Hw4MemoryManager that the node belongs to, and the second says which node in that manager's memory it represents. An Hw4Node supports the following methods, implemented as described:

Hw4Node(Hw4MemoryManager m, int nodeLocation)

This sets the Hw4Node's manager to m and its current field to nodeLocation. Only your Hw4MemoryManager code and the Hw4Node's getNode is allowed to call this constructor.

int get(NodeComponent type)

Here NodeComponent is an enum consisting of CURRENT, VALUE, PARENT, LEFT, RIGHT. This method looks up in manager.memory the index current plus the appropriate offset for the given type and returns the value. If the type is CURRENT then the field current is returned.

Hw4Node getNode(NodeComponent type)

This method looks up in manager.memory the index current plus the appropriate offset for the given type and returns a Hw4Node corresponding to that index.

set(NodeComponent type, int value)

This methods uses type to set the corresponding component of the `i`th node in manager.memory to value.

Hw4Tree has two field variables: Hw4Node root and Hw4MemoryManager manager. An Hw4Tree supports the following methods:

Hw4Tree(Hw4MemoryManager m)

The constructor for an Hw4Tree just sets the root field to null and set m into the manager field.

void insert(int value)

Inserts a new value into the Hw4Tree. This should involve a call to an implementation of the book's pseudo-code for TREE-INSERT(root, value). If there is not enough memory for the insert it should through an exception.

void delete(int value)

Delete a value from the Hw4Tree, if present. First, this function does a search to see if value is in the tree. If not, it should throw an exception. If it is, it obtains a node z storing value. It then calls an implementation of the book's pseudo-code for TREE-DELETE(root, z).

void printMin()

This prints the minimum value stored in the Hw4Tree followed by a newline. It should be implemented by a call to an implementation of the book's pseudo-code for TREE-MINIMUM(root).

void printMax()

This prints the maximum value stored in the Hw4Tree followed by a newline. It should be implemented by a call to an implementation of the book's pseudo-code for TREE-MAXIMUM(root).

void printSearch(int value)

Does a look-up in the binary search tree for value. If found it prints value, otherwise it prints NIL.

void printInorder()

Does an in-order traversal of the binary search tree. For each node in the tree it prints a space followed by that node's value. After the last node printed, it print a newline. It should be implemented by a call to an implementation of the book's pseudo-code for INORDER-TREE-WALK(root).

The class Hw4 serves as a driver program for the above classes. It will be run from the command line with a syntax like:

java Hw4 size command_1 command_2 ... command_n 

On such an input Hw4 constructs a Hw4MemoryManager and a Hw4Tree that uses that manager for memory. Here size is the number of nodes in the Hw4MemoryManager that Hw4 constructs. Commands can either be a positive integer, which means insert that value into the Hw4Tree; a negative integer, which means delete that value from the Hw4Tree; `mem` which means print the Hw4MemoryManager's memory; `min`, which means print the minimum value currently in the tree; `max`, which means print the maximum value currently in the tree; `s` followed by an integer means call printSearch for that integer in the tree; finally, `text{sort}` means call printInorder() on the tree. Below are some example inputs and outputs:

>java Hw4 1 7 mem
 7 -1 -1 -1
>java Hw4 3 7 5 min
 5
>java Hw4 3 7 5 -7 s7 max
NIL
 5
>java Hw4 10 7 5 9 17 2 -5 sort
 2 7 9 17 

As a last part of your assignment I would like you to make a file test.bat with a sequence of java Hw4 ... lines that would be suitable to test each of the public methods of each of the classes you have written. In a separate readme.txt explain what each of your tests is supposed to be checking. The grader will run your tests, but will also run additional tests and look at your code to determine whether it is operating correctly.

Point Breakdown